import collections
import random


class Solution(object):
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        balance = collections.defaultdict(int)
        for item in transactions:
            balance[item[0]] += item[2]
            balance[item[1]] -= item[2]
        user = len(balance)
        p_count = {}
        n_count = {}
        for key in balance:
            if balance[key] > 0:
                if balance[key] in p_count:
                    p_count[balance[key]] += 1
                else:
                    p_count[balance[key]] = 1
            if balance[key] < 0:
                if balance[key] in n_count:
                    n_count[balance[key]] += 1
                else:
                    n_count[balance[key]] = 1

        def search(p, n):
            count = 0
            min_count = user
            for key in p:
                if -key in n:
                    num = min(p[key], n[-key])
                    p[key] -= num
                    n[- key] -= num
                    count += num
            new_p = {}
            new_n = {}
            for key in p:
                if p[key] > 0:
                    new_p[key] = p[key]
            for key in n:
                if n[key] > 0:
                    new_n[key] = n[key]
            if len(new_p) == 0 and len(new_n) == 0:
                return count
            n_key = random.choice(list(new_n.keys()))
            new_n[n_key] -= 1
            if new_n[n_key] == 0:
                new_n.pop(n_key)
            for key in new_p:
                next_p = new_p.copy()
                next_n = new_n.copy()
                next_p[key] -= 1
                if next_p[key] == 0:
                    next_p.pop(key)
                if key + n_key > 0:
                    if key + n_key in next_p:
                        next_p[key + n_key] += 1
                    else:
                        next_p[key + n_key] = 1
                else:
                    if key + n_key in next_n:
                        next_n[key + n_key] += 1
                    else:
                        next_n[key + n_key] = 1
                min_count = min(min_count, count + 1 + search(next_p, next_n))
            return min_count

        if len(p_count) == 0 and len(n_count) == 0:
            return 0
        return search(p_count, n_count)


data = Solution()
transactions = [[0, 1, 10], [2, 0, 5]]
print(data.minTransfers(transactions))
# 1
transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]
print(data.minTransfers(transactions))
# 2
transactions = [[0, 2, 1], [1, 2, 3], [2, 3, 2], [2, 4, 2], [3, 0, 2]]
print(data.minTransfers(transactions))
# 6
transactions = [[1, 0, 18], [2, 1, 9], [4, 3, 11], [5, 4, 10], [5, 6, 7], [7, 6, 5], [8, 7, 3]]
print(data.minTransfers(transactions))
